#include <iostream>

using namespace std;

struct Node {
    int key;
    int priority;
    int size;
    Node* left;
    Node* right;

    Node() : key(0), priority(0), size(1), left(NULL), right(NULL) {}
    Node(int k, int p) : key(k), size(1), priority(p), left(NULL), right(NULL) {}
};

int getSize(Node* t){
    return (t == NULL) ? 0 : t->size;
}

void updateSize(Node* t) {
    t->size = getSize(t->left) + getSize(t->right) + 1;
}

Node* merge(Node* l, Node* r) {
    if (l == NULL) { return r; }
    if (r == NULL) { return l; }

    if (l->priority > r->priority) {
        l->right = merge(l->right, r);
        updateSize(l);  
        return l;
    } else {
        r->left = merge(l, r->left);
        updateSize(r); 
        return r;
    }
}

void split(Node* t, int key, Node** l, Node** r) {
    if (t == NULL) {
        *l = NULL;
        *r = NULL;
        return;
    }

    if (t->key < key) {
        *l = t;
        split(t->right, key, &((*l)->right), r);
        updateSize(*l); 
    } else {
        *r = t;
        split(t->left, key, l, &((*r)->left));
        updateSize(*r); 
    }
}

void insert (Node** t, Node* n) {
    if (*t == NULL) { *t = n; }
    else {
        if (n->priority > (*t)->priority) {
            split(*t, n->key, &(n->left), &(n->right));
            *t = n;
        } else {
            if (n->key < (*t)->key) insert(&((*t)->left), n);
            else insert(&((*t)->right), n);
        }
    }
    updateSize(*t); 
}

void remove(Node** t, int key) {
    if ((*t)->key == key) {
        *t = merge((*t)->left, (*t)->right);
    } else {
        if (key < (*t)->key) remove(&((*t)->left), key);
        else remove(&((*t)->right), key);
    }
    updateSize(*t); 
}

void print(Node* t) {
    if (t == NULL) return;

    print(t->left);
    cout<<t->key<<" "<<endl;
    print(t->right);
}

int getKStatistics(Node* t, int k) {
     while (t != NULL) {
        int sizeLeft = getSize(t->left);

        if (sizeLeft == k) return t->key;

        if (sizeLeft < k) {
            t = t->right;
            k -= sizeLeft + 1;
        } else {
            t = t->left;
        }
    }

    return NULL;
}

int main() {
    Node* tree = NULL;
    int a;

    for (int i = 0; i < 100; ++i) {
        a = i;
        Node* tmp = new Node(a, rand());
        insert(&tree, tmp);
    }

    print(tree);
    cout<<endl;
    cout<<getKStatistics(tree, 10)<<endl;

    system("pause");
    return 0;
}